﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace EasyLib.DataStructure
{
    public static class TreeVisitor
    {
        /// <summary>
        /// <code>
        /// foreach (var control in groupBox2.VisitDepthFirst<Control>(c => c.Controls.Cast<Control>()))
        ///{
        /// control.Text = "Done";
        ///}
        /// </code>
        ///Likewise visiting all nodes in an xml document is done as follows
        /// <code>
        ///foreach (XmlNode childNode in xmlDocument.VisitDepthFirst<XmlNode>(n => n.ChildNodes.Cast<XmlNode>()))
        ///{
        ///}
        /// </code>
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="root"></param>
        /// <param name="childSelector"></param>
        /// <returns></returns>
        public static IEnumerable<T> VisitDepthFirst<T>(this T root, Func<T, IEnumerable<T>> childSelector)
        {
            if (root == null) yield break;
            // we return the root
            yield return root;
            // then we do a recursive Depth first search of all children and yield each item we find
            foreach (var child in childSelector(root).SelectMany(c => c.VisitDepthFirst(childSelector)))
            {
                yield return child;
            }
        }

        static public IEnumerable<T> VisitBreathFirst<T>(this T root, Func<T, IEnumerable<T>> childSelector)
        {
            if (root == null) yield break;
            Queue<T> open = new Queue<T>();
            // the open queue contains the items that have already been visited, but who's children have not
            yield return root;
            open.Enqueue(root);
            while (open.Count > 0)
            {
                T item = open.Dequeue();
                foreach (T child in childSelector(item))
                {
                    yield return child;
                    open.Enqueue(child);
                }
            }
        }
    }
}
